package leetcode_动态规划;

/**
 * 最长回文子串
 * 算法：动态规划
 *
 * @author yezh
 * @date 2024/5/20 9:34
 */
public class _05 {

    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;
        // dp[i][j]: s[i...j] 是否是回文串
        boolean[][] dp = new boolean[len][len];
        int maxLen = 1, l = 0, r = 0;
        for (int i = 0; i < len; i++) dp[i][i] = true;
        for (int j = 1; j < len; j++)
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) != s.charAt(j)) dp[i][j] = false;
                else dp[i][j] = j - i < 3 || dp[i + 1][j - 1];
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1;
                    l = i;
                    r = j;
                }
            }
        return s.substring(l, r + 1);
    }

    public String longestPalindrome_中心扩散(String s) {
        int len = s.length();
        if (len < 3) return s;
        String ans = "";
        for (int i = 0; i < len; i++) {
            // 奇数回文串
            int l = i - 1, r = i + 1;
            String sub = getString(l, r, s);
            if (sub.length() > ans.length()) ans = sub;

            // 偶数回文串
            l = i - 1;
            r = i;
            sub = getString(l, r, s);
            if (sub.length() > ans.length()) ans = sub;
        }
        return ans;
    }

    String getString(int l, int r, String s) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

}
